package leetcode.jianzhioffer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-03 09:45
 **/
public class JianZhiOffer34 {
    List<List<Integer>> list = new LinkedList<>();
    Deque<Integer> deque = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return list;
    }

    private void dfs(TreeNode node, int target) {
        if (node == null) {
            return;
        }
        deque.offer(node.val);
        target -= node.val;
        if (node.left == null && node.right == null && target == 0) {
            list.add(new LinkedList<>(deque));
        }
        dfs(node.left, target);
        dfs(node.right, target);
        deque.pollLast();
    }
}

class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode() {}
   TreeNode(int val) { this.val = val; }
   TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
}
